// OpentTxl-C Version 11 transformer
// J.R. Cordy, Jan 2023

// Copyright 2023, James R. Cordy and others

// Permission is hereby granted, free of charge, to any person obtaining a copy of this software 
// and associated documentation files (the “Software”), to deal in the Software without restriction, 
// including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, 
// and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, 
// subject to the following conditions:

// The above copyright notice and this permission notice shall be included in all copies 
// or substantial portions of the Software.

// THE SOFTWARE IS PROVIDED “AS IS”, WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, 
// INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE 
// AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, 
// DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

// The OpenTxl transformer.
// Takes as input the input parse tree created by the parser and applies the transformation rules 
// in the rule table compiled by the rule compiler to create the transformed parse tree.

// Modification Log

// v11.0 Initial revision, adapted from OpenTxl 11.0

// v11.3 Added multiple skipping criteria for both patterns and deconstructors

#define XFORM

// I/O, strings, memory allocation
#include "support.h"

// Global modules
#include "locale.h"
#include "limits.h"
#include "options.h"
#include "tokens.h"
#include "trees.h"
#include "errors.h"
#include "shared.h"
#include "charset.h"
#include "idents.h"

// Compiler modules
#include "symbols.h"
#include "rules.h"

// Reflection modules
#include "scan.h"
#include "parse.h"
#include "unparse.h"

// Check interface consistency
#include "xform.h"

// Called rule activation environments

// In order to avoid an artificial limit on the number of parameters and local variables in a rule,
// we store the value bindings for all of them as frames in a single array

int transformer_maxTotalValues; // maxCallDepth * avgLocalVars
array (treePT, transformer_valueTP);
int transformer_valueCount;     // 0

// Rule call activation records
struct transformer_ruleEnvironmentT *transformer_callEnvironment;  // [0 .. maxCallDepth]
int transformer_callDepth;      // 0

// Pattern search stack - this same stack is used for all searching
static int transformer_maxSearchDepth;  // maxParseDepth * 4
struct transformer_searchStackEntry {
    kidPT kidsKP, endKP;
};
// 1-origin [1 .. maxSearchDepth]
static struct transformer_searchStackEntry *transformer_searchStack;
static int transformer_searchTop;       // 0

// Match stack - used only in matchTreeToPattern
static int transformer_maxMatchDepth;   // maxParseDepth
struct transformer_matchStackEntry {
    kidPT patternKidsKP, patternEndKP;
    kidPT treeKidsKP;
};
// 1-origin [1 .. maxMatchDepth]
static struct transformer_matchStackEntry *transformer_matchStack; 

#ifdef PROFILER
static int transformer_searchcycles;
static int transformer_matchcycles;
struct transformer_ruleStatisticsT {
    int calls;
    int matches;
    int searchcycles;
    int matchcycles;
    int trees;
    int kids;
};
// 1-origin [1 .. maxMatchDepth]
static struct transformer_ruleStatisticsT *transformer_ruleStatistics;
#endif

#ifdef DEBUGGER
    // The TXL interactive debugger
    #include "debug.h"
#endif

// Name of rule currently being applied (for error messages and such)
int transformer_applyingRuleName;  // empty_T
int transformer_callingRuleName;   // empty_T; used only by predefined rules, for error messages

// Statistics on tree sharing
static int transformer_copies;      // 0
static int transformer_noncopies;  // 0

// Treespace used by compiled TXL program - filled in by xform.applyMainRule
// We don't disturb the trees and kids of the compiled TXL program when recovering garbage
treePT transformer_lastCompileTree;  // nilTree
kidPT transformer_lastCompileKid;    // nilKid

// Garbage recovery
#include "garbage.h"

// Garbage recovery stats
static int transformer_nGarbageRecoveries;  // 0
static int transformer_currentGCdepth;      // 0

static bool transformer_matchTreeToPattern (const treePT argPatternTP, const treePT argTreeTP, struct transformer_ruleEnvironmentT *ruleEnvironment)
{
    // Rationale for the order of the following logic is the typical frequency
    // profile of the cases in production use at Legasys.  Here is a sample:
    
    // choose           91040191        82.2%
    // firstTime        11178871        10.1%
    // subsequentUse     3893958         3.5%
    // repeat            2386210         2.2%
    // id                2225540         2.0%
    // order               13748         0.0%
    // empty                1474         0.0%
    // literal               183         0.0%

    treePT patternTP = argPatternTP;
    treePT treeTP = argTreeTP;
    int matchTop = 0;

    while (true) {
        assert ((tree_trees[patternTP].kidsKP >= 0) && (tree_trees[patternTP].kidsKP <= maxKids));
        assert ((tree_trees[treeTP].kidsKP >= 0) && (tree_trees[treeTP].kidsKP <= maxKids));

        #ifdef PROFILER
        transformer_matchcycles += 1;
        #endif

        if (tree_trees[patternTP].kind == treeKind_choose) {
            // choose tree
            if ((tree_trees[treeTP].name != tree_trees[patternTP].name) || (tree_trees[treeTP].kind != treeKind_choose)) {
                return (false);
            }

            patternTP = tree_kids[tree_trees[patternTP].kidsKP];
            treeTP = tree_kids[tree_trees[treeTP].kidsKP];

        } else if (tree_trees[patternTP].kind == treeKind_firstTime) {
            // binding a TXL variable
            // the count field tells us the locals index!
            const struct ruleLocalT *localVar = 
                &(rule_ruleLocals[ruleEnvironment->localsListAddr->localsBase + tree_trees[patternTP].count]);

            if (!(  // if types do not match, in one of these ways ...

                    (   // types match exactly
                        (tree_trees[treeTP].name == localVar->basetypename) 
                        // and we don't mistake a literal id or other token for a type
                        && (!((tree_trees[treeTP].kind >= firstLiteralKind) && (tree_trees[treeTP].kind <= lastLiteralKind)))
                        // and we don't allow empty repeats/lists to match [repeat+]/[list+]
                        && (!((localVar->basetypename != localVar->typename_) 
                                && (tree_trees[tree_kids[tree_trees[treeTP].kidsKP]].kind == treeKind_empty)))
                    )
                ||  
                    (   // type matches kind
                        kindType[tree_trees[treeTP].kind] == localVar->basetypename
                    )

                || 
                    (   // type is [key] and tree is a keyword
                        (localVar->basetypename == key_T) 
                        && (tree_trees[treeTP].kind == treeKind_literal) && scanner_keyP (tree_trees[treeTP].name)
                    )
                || 
                    (   // type is [token] and tree is a non-keyword
                        (localVar->basetypename == token_T) 
                        && (tree_trees[treeTP].kind == treeKind_literal) && (!scanner_keyP (tree_trees[treeTP].name))
                    )
                ||
                    (   // type is [any]
                        (localVar->basetypename == any_T)
                    )
               )) 
            {
                return (false);
            }

            // bind the local variable to the tree
            transformer_valueTP[ruleEnvironment->valuesBase + tree_trees[patternTP].count] = treeTP;

            if (tree_trees[patternTP].count == 1) {
                // only need this fact for the first parameter of a rule
                ruleEnvironment->parentrefs = 9;  // anything > 1
            }

            // Pop any completed matches ...
            while (true) {
                if (matchTop == 0) {
                    return (true);
                }
                if (transformer_matchStack[matchTop].patternKidsKP < transformer_matchStack[matchTop].patternEndKP) 
                    break;
                matchTop -= 1;
            }

            // ... and move on to the next subtree in the sequence
            assert ((matchTop > 0) && (transformer_matchStack[matchTop].patternKidsKP < transformer_matchStack[matchTop].patternEndKP));

            transformer_matchStack[matchTop].patternKidsKP += 1;
            patternTP = tree_kids[transformer_matchStack[matchTop].patternKidsKP];
            transformer_matchStack[matchTop].treeKidsKP += 1;
            treeTP = tree_kids[transformer_matchStack[matchTop].treeKidsKP];

        } else if (tree_trees[patternTP].kind == treeKind_subsequentUse) {
            // matching a bound variable
            // the count field tells us the ruleLocals index!
            patternTP = transformer_valueTP[ruleEnvironment->valuesBase + tree_trees[patternTP].count];

        } else if ((tree_trees[patternTP].kind) <= lastStructureKind) {
            assert ((tree_trees[patternTP].kind == treeKind_order) 
                || (tree_trees[patternTP].kind == treeKind_repeat) || (tree_trees[patternTP].kind == treeKind_list));
            // order tree
            if ((tree_trees[treeTP].name != tree_trees[patternTP].name) || (tree_trees[treeTP].kind != tree_trees[patternTP].kind)) {
                return (false);
            }

            assert (matchTop < transformer_maxMatchDepth);  // can easily prove this

            matchTop += 1;
            transformer_matchStack[matchTop].patternKidsKP = tree_trees[patternTP].kidsKP;
            transformer_matchStack[matchTop].patternEndKP = 
                transformer_matchStack[matchTop].patternKidsKP + tree_trees[patternTP].count - 1;
            patternTP = tree_kids[tree_trees[patternTP].kidsKP];
            transformer_matchStack[matchTop].treeKidsKP = tree_trees[treeTP].kidsKP;
            treeTP = tree_kids[tree_trees[treeTP].kidsKP];

        } else {
            assert (tree_trees[patternTP].kind >= firstLeafKind);

            if (tree_trees[patternTP].kind == treeKind_empty) {
                if (tree_trees[treeTP].kind != treeKind_empty) {
                    return (false);
                }
            } else {
                if (tree_trees[treeTP].name != tree_trees[patternTP].name) {
                    return (false);
                }

                if (tree_trees[treeTP].kind != tree_trees[patternTP].kind) {
                    if (tree_trees[patternTP].kind == treeKind_literal) {
                        if (!((tree_trees[treeTP].kind == treeKind_literal) || (tree_trees[treeTP].kind == treeKind_id))) {
                            return (false);
                        }
                    } else {
                        return (false);
                    }
                }
            }

            // Pop any completed matches ...
            while (true) {
                if (matchTop == 0) {
                    return (true);
                }
                if (transformer_matchStack[matchTop].patternKidsKP < transformer_matchStack[matchTop].patternEndKP) 
                    break;
                matchTop -= 1;
            }

            // ... and move on to the next subtree in the sequence
            assert ((matchTop > 0) && (transformer_matchStack[matchTop].patternKidsKP < transformer_matchStack[matchTop].patternEndKP));

            transformer_matchStack[matchTop].patternKidsKP += 1;
            patternTP = tree_kids[transformer_matchStack[matchTop].patternKidsKP];
            transformer_matchStack[matchTop].treeKidsKP += 1;
            treeTP = tree_kids[transformer_matchStack[matchTop].treeKidsKP];
        }
    }
}

static void transformer_searchdepth_error (const tokenT ruleName)
{
    string context, message;
    stringprintf (context, "rule/function '%s'", *ident_idents[ruleName]);
    stringprintf (message, "Maximum search depth (%d) exceeded when searching for a pattern match (a larger size is required for this transform)", 
        transformer_maxSearchDepth);
    error (context, message, FATAL, 501);
}

static bool transformer_searchTreeForDeconstructPattern (const treePT argPatternTP, const treePT argTreeTP, 
    struct transformer_ruleEnvironmentT *ruleEnvironment)
{
    // Rationale for the order of the following logic is the typical frequency
    // profile of the cases in production use at Legasys.  Here is a sample:

    // kind of treeTP, per cycle :
    // literal          20292374        26.5%
    // repeat           15528787        20.3%
    // empty            13752757        17.9%
    // id               10819315        14.1%
    // choose            6210380         8.1%
    // order             5789258         7.6%
    // stringlit         2207113         2.8%
    // number            2060547         2.6%

    treePT treeTP = argTreeTP;
    treePT patternTP = argPatternTP;
    int searchTop = transformer_searchTop;
    int searchBase = transformer_searchTop;

    if (tree_trees[patternTP].kind == treeKind_subsequentUse) {
        // use concrete pattern
        patternTP = transformer_valueTP[ruleEnvironment->valuesBase + tree_trees[patternTP].count];
    }

    while (true) {
        assert ((tree_trees[patternTP].kidsKP >= 0) && (tree_trees[patternTP].kidsKP <= maxKids));
        assert ((tree_trees[treeTP].kidsKP >= 0) && (tree_trees[treeTP].kidsKP <= maxKids));

        #ifdef PROFILER
            transformer_searchcycles += 1;
        #endif

        if (((tree_trees[treeTP].kind == tree_trees[patternTP].kind) || (tree_trees[patternTP].kind == treeKind_firstTime)) 
                    && transformer_matchTreeToPattern (patternTP, treeTP, ruleEnvironment)) {
            transformer_searchTop = searchBase;
            return (true);
        }

        if (tree_trees[treeTP].kind >= firstLeafKind) {
            // A terminal -
            // Pop any completed sequences ...
            while (true) {
                if (searchTop == searchBase) {
                    transformer_searchTop = searchBase;
                    return (false);
                }
                if (transformer_searchStack[searchTop].kidsKP < transformer_searchStack[searchTop].endKP) break;
                searchTop -= 1;
            }
            // ... and move on to the next subtree in the sequence
            assert (((searchTop > searchBase) 
                && ((transformer_searchStack[searchTop].kidsKP) < (transformer_searchStack[searchTop].endKP))));
            transformer_searchStack[searchTop].kidsKP += 1;
            treeTP = tree_kids[transformer_searchStack[searchTop].kidsKP];

        } else if (tree_trees[treeTP].kind == treeKind_choose) {
            // One child - just go down to it (no need to come back)
            treeTP = tree_kids[tree_trees[treeTP].kidsKP];

        } else {
            // Push a new sequence of subtrees to check
            assert ((tree_trees[treeTP].kind == treeKind_order) || (tree_trees[treeTP].kind == treeKind_repeat) 
                || (tree_trees[treeTP].kind == treeKind_list));

            if (searchTop >= transformer_maxSearchDepth) {
                transformer_searchdepth_error (transformer_applyingRuleName);
            }

            searchTop += 1;
            transformer_searchStack[searchTop].kidsKP = tree_trees[treeTP].kidsKP;
            transformer_searchStack[searchTop].endKP = transformer_searchStack[searchTop].kidsKP + tree_trees[treeTP].count - 1;
            treeTP = tree_kids[tree_trees[treeTP].kidsKP];
        }
    }
}

static bool transformer_searchTreeForDeconstructPatternSkipping (const treePT argPatternTP, const treePT argTreeTP, 
    struct transformer_ruleEnvironmentT *ruleEnvironment, tokenT skipName, tokenT skipName2, tokenT skipName3)
{
    // Rationale for the order of the following logic is the typical frequency
    // profile of the cases in production use at Legasys.  Here is a sample:

    // kind of treeTP, per cycle :
    // literal          20292374        26.5%
    // repeat           15528787        20.3%
    // empty            13752757        17.9%
    // id               10819315        14.1%
    // choose            6210380         8.1%
    // order             5789258         7.6%
    // stringlit         2207113         2.8%
    // number            2060547         2.6%

    treePT treeTP = argTreeTP;
    treePT patternTP = argPatternTP;
    int searchTop = transformer_searchTop;
    int searchBase = transformer_searchTop;

    if (tree_trees[patternTP].kind == treeKind_subsequentUse) {
        // use concrete pattern
        patternTP = transformer_valueTP[ruleEnvironment->valuesBase + tree_trees[patternTP].count];
    }

    while (true) {
        assert ((tree_trees[patternTP].kidsKP >= 0) && (tree_trees[patternTP].kidsKP <= maxKids));
        assert ((tree_trees[treeTP].kidsKP >= 0) && (tree_trees[treeTP].kidsKP <= maxKids));

        #ifdef PROFILER
            transformer_searchcycles += 1;
        #endif

        if (((tree_trees[treeTP].kind == tree_trees[patternTP].kind) || (tree_trees[patternTP].kind == treeKind_firstTime)) 
                    && transformer_matchTreeToPattern (patternTP, treeTP, ruleEnvironment)) {
            transformer_searchTop = searchBase;
            return (true);
        }

        if ((tree_trees[treeTP].kind >= firstLeafKind) || (tree_trees[treeTP].name == skipName) ||
                (tree_trees[treeTP].name == skipName2) || (tree_trees[treeTP].name == skipName3)) {
            // A terminal -
            // Pop any completed sequences ...
            while (true) {
                if (searchTop == searchBase) {
                    transformer_searchTop = searchBase;
                    return (false);
                }
                if (transformer_searchStack[searchTop].kidsKP < transformer_searchStack[searchTop].endKP) break;
                searchTop -= 1;
            }
            // ... and move on to the next subtree in the sequence
            assert (((searchTop > searchBase) 
                && (transformer_searchStack[searchTop].kidsKP < transformer_searchStack[searchTop].endKP)));
            transformer_searchStack[searchTop].kidsKP += 1;
            treeTP = tree_kids[transformer_searchStack[searchTop].kidsKP];

        } else if (tree_trees[treeTP].kind == treeKind_choose) {
            // One child - just go down to it (no need to come back)
            treeTP = tree_kids[tree_trees[treeTP].kidsKP];

        } else {
            // Push a new sequence of subtrees to check
            assert ((tree_trees[treeTP].kind == treeKind_order) || (tree_trees[treeTP].kind == treeKind_repeat) 
                || (tree_trees[treeTP].kind == treeKind_list));

            if (searchTop >= transformer_maxSearchDepth) {
                transformer_searchdepth_error (transformer_applyingRuleName);
            }

            searchTop += 1;
            transformer_searchStack[searchTop].kidsKP = tree_trees[treeTP].kidsKP;
            transformer_searchStack[searchTop].endKP = transformer_searchStack[searchTop].kidsKP + tree_trees[treeTP].count - 1;
            treeTP = tree_kids[tree_trees[treeTP].kidsKP];
        }
    }
}

static bool transformer_searchTreeForDeconstructPatternSkippingRepeat (const treePT argPatternTP, const treePT argTreeTP, 
    struct transformer_ruleEnvironmentT *ruleEnvironment)
{
    treePT treeTP = argTreeTP;
    treePT patternTP = argPatternTP;

    if (tree_trees[patternTP].kind == treeKind_subsequentUse) {
        // use concrete pattern
        patternTP = transformer_valueTP[ruleEnvironment->valuesBase + tree_trees[patternTP].count];
    }

    // walk the repeat looking for the matching element
    while (true) {
        if (tree_trees[tree_kids[tree_trees[treeTP].kidsKP]].kind == treeKind_empty) break;

        #ifdef PROFILER
            transformer_searchcycles += 1;
        #endif

        const treePT elementTP = tree_kids[tree_trees[treeTP].kidsKP];

        if (((tree_trees[elementTP].kind == tree_trees[patternTP].kind) || (tree_trees[patternTP].kind == treeKind_firstTime)) 
                && transformer_matchTreeToPattern (patternTP, elementTP, ruleEnvironment)) {
            return (true);
        }

        treeTP = tree_kids[tree_trees[treeTP].kidsKP + 1];
    }

    return (false);
}

static void transformer_calldepth_error (const tokenT ruleName, const tokenT calledRuleName)
{
    string context, message;
    stringprintf (context, "rule/function '%s'", *ident_idents[ruleName]);
    stringprintf (message, "Maximum call depth (%d) exceeded when calling rule/function '%s' (Probably cause: infinite recursion)",
        maxCallDepth, *ident_idents[calledRuleName]);
    error (context, message, FATAL, 502);
}

static void transformer_global_error (const tokenT ruleName, const tokenT partName)
{
    string context, message;
    stringprintf (context, "rule/function '%s'", *ident_idents[ruleName]);
    stringprintf (message, "Imported global variable '%s' has not been bound", *ident_idents[partName]);
    error (context, message, FATAL, 503);
}

static void transformer_assert_error (const tokenT ruleName, const tokenT partName)
{
    string context, message;
    stringprintf (context, "rule/function '%s'", *ident_idents[ruleName]);
    stringprintf (message, "Assertion on '%s' failed", *ident_idents[partName]);
    error (context, message, FATAL, 504);
}

static void transformer_each_error (const tokenT ruleName)
{
    string context;
    stringprintf (context, "rule/function '%s'", *ident_idents[ruleName]);
    error (context, "'each' limited to at most two parameters", LIMIT_FATAL, 505);
}

static void transformer_applyRule (const int ruleIndex, struct transformer_ruleEnvironmentT *ruleEnvironment, 
    const treePT originalTP, treePT *resultTP, bool *matched);

static void transformer_applyRules (const kidPT ruleCallsKP, struct transformer_ruleEnvironmentT *ruleEnvironment, 
    treePT *resolvedTreeTP, bool *someMatched, bool *allMatched)
{
    const tokenT thisRuleName = transformer_applyingRuleName;

    *someMatched = false;
    *allMatched = true;

    assert (ruleCallsKP != nilKid);

    kidPT localRuleCallsKP = ruleCallsKP;

    while (true) {
        bool subruleMatched;

        const treePT ruleCallTP = tree_kids[localRuleCallsKP];

        assert (tree_trees[ruleCallTP].kind == treeKind_ruleCall);

        // rule index encoded in the name field of the call!
        int ruleIndex = tree_trees[ruleCallTP].name;

        // allocate a new call activation record for the subrule call
        if (transformer_callDepth == maxCallDepth) {
            transformer_calldepth_error (transformer_applyingRuleName, rule_rules[ruleIndex].name);
        } else {
            transformer_callDepth += 1;
        }

        struct transformer_ruleEnvironmentT *subruleEnvironment = &(transformer_callEnvironment[transformer_callDepth]);

        // remember the call depth (for garbage collection)
        subruleEnvironment->depth = transformer_callDepth;

        // remember the rule name (for debugging)
        subruleEnvironment->name = rule_rules[ruleIndex].name;

        // attach the rule's symbol table for formal parameters and local variables
        subruleEnvironment->localsListAddr = &(rule_rules[ruleIndex].localVars);
        subruleEnvironment->valuesBase = transformer_valueCount;

        // allocate value bindings for formals and local variables of the rule
        if ((transformer_valueCount + rule_rules[ruleIndex].localVars.nlocals) > transformer_maxTotalValues) {
            transformer_calldepth_error (transformer_applyingRuleName, rule_rules[ruleIndex].name);
        } else {
            transformer_valueCount += rule_rules[ruleIndex].localVars.nlocals;
        }

        // remember the scope tree
        subruleEnvironment->scopeTP = *resolvedTreeTP;

        // and the partially resolved replacement tree
        subruleEnvironment->resultTP = nilTree;

        // and the partially resolved new scope tree
        subruleEnvironment->newscopeTP = nilTree;

        // bind values to the formal names
        kidPT litAndVarActualsLeftKP = tree_trees[ruleCallTP].kidsKP;
        int eachIndex = 0;

        for (int arg = 1; arg <= rule_rules[ruleIndex].localVars.nformals; arg++) {
            const treePT litOrVarActualTP = tree_kids[litAndVarActualsLeftKP];

            if (tree_trees[litOrVarActualTP].kind == treeKind_subsequentUse) {
                // the count field tells us the rule's local symbol table index
                transformer_valueTP[subruleEnvironment->valuesBase + arg] = 
                    transformer_valueTP[ruleEnvironment->valuesBase + tree_trees[litOrVarActualTP].count];

                if (arg == 1) {
                    // only need this fact for the first parameter of a rule; optimizes built-in rules
                    subruleEnvironment->parentrefs = 
                        rule_ruleLocals[ruleEnvironment->localsListAddr->localsBase + tree_trees[litOrVarActualTP].count].refs;
                }

                // and the kidsKP tells us if it's an 'each'ed argument
                if (tree_trees[litOrVarActualTP].kidsKP != nilKid) {
                    if (eachIndex == 0) {
                        eachIndex = arg;
                    }
                }

            } else {
                transformer_valueTP[subruleEnvironment->valuesBase + arg] = litOrVarActualTP;

                if (arg == 1) {
                    // only need this fact for the first parameter of a rule; optimizes built-in rules
                    subruleEnvironment->parentrefs = 1;
                }
            }

            litAndVarActualsLeftKP += 1;
        }

        // initialize unbound local symbol bindings to nil, for garbage collection
        for (int loc = rule_rules[ruleIndex].localVars.nformals + 1; loc <= rule_rules[ruleIndex].localVars.nlocals; loc++) {
            transformer_valueTP[subruleEnvironment->valuesBase + loc] = nilTree;
        }

        if (eachIndex == 0) {
            // simple arguments
            treePT resultTP;

            transformer_applyRule (ruleIndex, subruleEnvironment, *resolvedTreeTP, &resultTP, &subruleMatched);

            *resolvedTreeTP = resultTP;
            *someMatched = *someMatched || subruleMatched;
            *allMatched = *allMatched && subruleMatched;
            ruleEnvironment->hasExported = (ruleEnvironment->hasExported) || (subruleEnvironment->hasExported);

        } else {
            // each specified; arguments each'ed must be lists or repeats
            // if only one arg, apply rule using each element of the list or repeat;
            // if two args, apply using corresponding pairs
            assert (tree_isListOrRepeat (transformer_valueTP[subruleEnvironment->valuesBase + eachIndex]));

            // first item in the repeat/list
            kidPT each1KP = tree_trees[transformer_valueTP[subruleEnvironment->valuesBase + eachIndex]].kidsKP;

            if (eachIndex == rule_rules[ruleIndex].localVars.nformals) {
                // one eached argument - special case for speed
                // run through repeat/list - calls with empty repeat/lists do nothing

                while (true) {
                    if (tree_trees[tree_kids[each1KP]].kind == treeKind_empty) break;

                    // remember the scope tree for EACH invocation!
                    subruleEnvironment->scopeTP = *resolvedTreeTP;

                    // and the partially resolved replacement
                    subruleEnvironment->resultTP = nilTree;

                    transformer_valueTP[subruleEnvironment->valuesBase + eachIndex] = tree_kids[each1KP];

                    treePT resultTP;
                    transformer_applyRule (ruleIndex, subruleEnvironment, *resolvedTreeTP, &resultTP, &subruleMatched);

                    *resolvedTreeTP = resultTP;
                    *someMatched = *someMatched || subruleMatched;
                    *allMatched = *allMatched && subruleMatched;
                    ruleEnvironment->hasExported = (ruleEnvironment->hasExported) || (subruleEnvironment->hasExported);

                    // next item in the repeat/list
                    each1KP = tree_trees[tree_kids[each1KP + 1]].kidsKP;
                }

            } else if (eachIndex + 1 == rule_rules[ruleIndex].localVars.nformals) {
                // two eached arguments - special case for speed
                assert (tree_isListOrRepeat (transformer_valueTP[subruleEnvironment->valuesBase + eachIndex + 1]));

                // first item in the second repeat/list
                kidPT each2KP = tree_trees[transformer_valueTP[subruleEnvironment->valuesBase + eachIndex + 1]].kidsKP;

                // run through repeat/list - calls with empty repeat/lists do nothing
                // lengths no longer need to be the same in TXL!

                while (true) {
                    if ((tree_trees[tree_kids[each1KP]].kind == treeKind_empty) 
                        || (tree_trees[tree_kids[each2KP]].kind == treeKind_empty)) break;

                    // remember the scope tree for EACH invocation!
                    subruleEnvironment->scopeTP = *resolvedTreeTP;

                    // and the partially resolved replacement
                    subruleEnvironment->resultTP = nilTree;

                    // bind argument values 
                    transformer_valueTP[subruleEnvironment->valuesBase + eachIndex] = tree_kids[each1KP];
                    transformer_valueTP[subruleEnvironment->valuesBase + eachIndex + 1] = tree_kids[each2KP];

                    treePT resultTP;
                    transformer_applyRule (ruleIndex, subruleEnvironment, *resolvedTreeTP, &resultTP, &subruleMatched);

                    *resolvedTreeTP = resultTP;
                    *someMatched = *someMatched || subruleMatched;
                    *allMatched = *allMatched && subruleMatched;
                    ruleEnvironment->hasExported = (ruleEnvironment->hasExported) || (subruleEnvironment->hasExported);

                    // next items in the repeats/lists 
                    each1KP = tree_trees[tree_kids[each1KP + 1]].kidsKP;
                    each2KP = tree_trees[tree_kids[each2KP + 1]].kidsKP;
                }

            } else {
                // general case - not implemented
                transformer_each_error (thisRuleName);
            }
        }

        // deallocate value bindings for rule local symbols 
        transformer_valueCount = subruleEnvironment->valuesBase;
        transformer_callDepth -= 1;
        localRuleCallsKP += 1;

        // any more rule calls?
        if (tree_kids[localRuleCallsKP] == nilTree) break;
    }

    transformer_applyingRuleName = thisRuleName;
}

static void transformer_resolveReplacementExpressions (treePT *resolvedReplacementTP, struct transformer_ruleEnvironmentT *ruleEnvironment)
{
    assert ((tree_trees[*resolvedReplacementTP].kidsKP >= 0) && (tree_trees[*resolvedReplacementTP].kidsKP <= maxKids));

    // Avoid multiple local vars
    treePT resolvedKidTP;

    switch (tree_trees[*resolvedReplacementTP].kind) {

        case treeKind_order:
            {
                kidPT replacementKidsKP = tree_trees[*resolvedReplacementTP].kidsKP;
                const kidPT endKP = replacementKidsKP + (tree_trees[*resolvedReplacementTP].count);

                assert (replacementKidsKP != nilKid);

                while (true) {
                    resolvedKidTP = tree_kids[replacementKidsKP];
                    transformer_resolveReplacementExpressions (&resolvedKidTP, ruleEnvironment);
                    tree_setKidTree (replacementKidsKP, resolvedKidTP);
                    replacementKidsKP += 1;
                    if (replacementKidsKP >= endKP) break;
                }
            }
            break;

        case treeKind_repeat:
            {
                kidPT replacementKidsKP = tree_trees[*resolvedReplacementTP].kidsKP;

                assert (replacementKidsKP != nilKid);

                while (true) {
                    resolvedKidTP = tree_kids[replacementKidsKP];
                    transformer_resolveReplacementExpressions (&resolvedKidTP, ruleEnvironment);
                    tree_setKidTree (replacementKidsKP, resolvedKidTP);
                    if (tree_trees[tree_kids[replacementKidsKP + 1]].kind != treeKind_repeat) break;
                    replacementKidsKP = tree_trees[tree_kids[replacementKidsKP + 1]].kidsKP;
                }

                resolvedKidTP = tree_kids[replacementKidsKP + 1];
                transformer_resolveReplacementExpressions (&resolvedKidTP, ruleEnvironment);
                tree_setKidTree (replacementKidsKP + 1, resolvedKidTP);
            }
            break;

        case treeKind_list:
            {
                kidPT replacementKidsKP = tree_trees[*resolvedReplacementTP].kidsKP;

                assert (replacementKidsKP != nilKid);

                while (true) {
                    resolvedKidTP = tree_kids[replacementKidsKP];
                    transformer_resolveReplacementExpressions (&resolvedKidTP, ruleEnvironment);
                    tree_setKidTree (replacementKidsKP, resolvedKidTP);
                    if (tree_trees[tree_kids[replacementKidsKP + 1]].kind != treeKind_list) break;
                    replacementKidsKP = tree_trees[tree_kids[replacementKidsKP + 1]].kidsKP;
                }

                resolvedKidTP = tree_kids[replacementKidsKP + 1];
                transformer_resolveReplacementExpressions (&resolvedKidTP, ruleEnvironment);
                tree_setKidTree (replacementKidsKP + 1, resolvedKidTP);
            }
            break;

        case treeKind_choose:
            {
                const kidPT replacementKidKP = tree_trees[*resolvedReplacementTP].kidsKP;

                assert (replacementKidKP != nilKid);

                resolvedKidTP = tree_kids[replacementKidKP];
                transformer_resolveReplacementExpressions (&resolvedKidTP, ruleEnvironment);
                tree_setKidTree ((kidPT) replacementKidKP, (treePT) resolvedKidTP);
            }
            break;

        case treeKind_literal: case treeKind_stringlit: case treeKind_charlit: case treeKind_number: case treeKind_id:
        case treeKind_comment: case treeKind_space: case treeKind_newline: case treeKind_srclinenumber: case treeKind_srcfilename:
        case treeKind_usertoken1: case treeKind_usertoken2: case treeKind_usertoken3: case treeKind_usertoken4: case treeKind_usertoken5:
        case treeKind_usertoken6: case treeKind_usertoken7: case treeKind_usertoken8: case treeKind_usertoken9: case treeKind_usertoken10:
        case treeKind_usertoken11: case treeKind_usertoken12: case treeKind_usertoken13: case treeKind_usertoken14: case treeKind_usertoken15:
        case treeKind_usertoken16: case treeKind_usertoken17: case treeKind_usertoken18: case treeKind_usertoken19: case treeKind_usertoken20:
        case treeKind_usertoken21: case treeKind_usertoken22: case treeKind_usertoken23: case treeKind_usertoken24: case treeKind_usertoken25:
        case treeKind_usertoken26: case treeKind_usertoken27: case treeKind_usertoken28: case treeKind_usertoken29: case treeKind_usertoken30:
        case treeKind_empty: case treeKind_token: case treeKind_key: case treeKind_upperlowerid: case treeKind_upperid: case treeKind_lowerupperid:
        case treeKind_lowerid: case treeKind_floatnumber: case treeKind_decimalnumber: case treeKind_integernumber:
            {
                return;
            }
            break;

        case treeKind_expression: case treeKind_lastExpression:
            {
                // the count field tells us the ruleLocals index!
                const int localIndex = tree_trees[*resolvedReplacementTP].count;
                const kidPT ruleCallsKP = tree_trees[*resolvedReplacementTP].kidsKP;

                // We must copy every variable reference in order to
                // avoid creating DAGs - unless it is used exactly once, 
                // or is the very last reference.

                if ((rule_ruleLocals[ruleEnvironment->localsListAddr->localsBase + localIndex].refs == 1)
                        || ((tree_trees[*resolvedReplacementTP].kind == treeKind_lastExpression) && (!(options_option[apply_print_p])))) {

                    #ifdef DEBUGGER
                    if ((options_option[rule_print_p]) && (options_option[sharing_p])) {
                        fprintf (stderr, "Did not copy '%s'", 
                            *ident_idents[rule_ruleLocals[ruleEnvironment->localsListAddr->localsBase + localIndex].name]);
                        if (tree_trees[*resolvedReplacementTP].kind == treeKind_lastExpression) {
                            fprintf (stderr, " (last ref)\n");
                        } else {
                            fprintf (stderr, " (refs = 1)\n");
                        }
                    }
                    #endif 

                    *resolvedReplacementTP = transformer_valueTP[ruleEnvironment->valuesBase + localIndex];
                    transformer_noncopies += 1;

                } else {
                    #ifdef DEBUGGER
                    const int oldKidCount = tree_kidCount;
                    const int oldTreeCount = tree_treeCount;
                    #endif

                    tree_copyTree (transformer_valueTP[ruleEnvironment->valuesBase + localIndex], resolvedReplacementTP);

                    #ifdef DEBUGGER
                    if ((options_option[rule_print_p]) && (options_option[sharing_p])) {
                        const int refs = rule_ruleLocals[ruleEnvironment->localsListAddr->localsBase + localIndex].refs;
                        fprintf (stderr, "Forced to copy '%s'", 
                            *ident_idents[rule_ruleLocals[ruleEnvironment->localsListAddr->localsBase + localIndex].name]);
                        fprintf (stderr, " (refs = %d) - cost %d trees and %d kids\n", refs, (tree_treeCount - oldTreeCount) + 1, 
                            (tree_kidCount - oldKidCount) + 1);
                    }
                    #endif

                    transformer_copies += 1;
                }

                if (ruleCallsKP != nilKid) {
                    // Now apply the subrules to it
                    bool someRulesSucceeded, allRulesSucceeded;
                    transformer_applyRules (ruleCallsKP, ruleEnvironment, resolvedReplacementTP, 
                        &someRulesSucceeded, &allRulesSucceeded);
                }
            }
            break;

        default :
            {
                error ("", "Fatal TXL error in resolveReplacementExpressions", INTERNAL_FATAL, 506);
            }
            break;
    }
}

static void transformer_makeReplacement (const treePT replacementTP, treePT *subTreeTP, struct transformer_ruleEnvironmentT *ruleEnvironment)
{
    try {

        assert (transformer_callEnvironment[transformer_callDepth].name == transformer_applyingRuleName);
        assert (ruleEnvironment->name == transformer_applyingRuleName); 

        treePT oldTreeTP;

        if (options_option[apply_print_p]) {
            // will this work with garbage collecting? -- NO!
            assert (tree_allocationStrategy == simple);

            if (*subTreeTP == nilTree) {
                oldTreeTP = nilTree;
            } else {
                tree_copyTree (*subTreeTP, &oldTreeTP);
            }
        }

        assert (replacementTP != nilTree);
                
        // The replacement is one thing we *must* copy every time,
        // since it will become part of the new parse tree.

        treePT resolvedReplacementTP;
        tree_copyTree (replacementTP, &resolvedReplacementTP);

        // Make sure that the garbage collector knows that we are working on this tree
        ruleEnvironment->resultTP = resolvedReplacementTP;

        transformer_resolveReplacementExpressions (&resolvedReplacementTP, ruleEnvironment);

        // Link in the resolved replacement for subTree by copying
        // the root tree of the replacement subtree into the root
        // tree of the original

        if (options_option[apply_print_p]) {
            if ((oldTreeTP != nilTree) && (!tree_sameTrees (oldTreeTP, resolvedReplacementTP))) {
                unparser_printLeaves (oldTreeTP, 0, false);
                fprintf (stderr, " ==> ");
                unparser_printLeaves (resolvedReplacementTP, 0, false);
                fprintf (stderr, " [%s]\n", *ident_idents[transformer_applyingRuleName]);
            }
        }

        // If sharing is done perfectly, it is not necessary to copy this!
        *subTreeTP = resolvedReplacementTP;

    } catch {

        if ((exception == OUTOFKIDS) || (exception == OUTOFTREES)) {
            // re-establish the rule call context and synchronize the call stack
            transformer_callDepth = ruleEnvironment->depth;
            transformer_valueCount = ruleEnvironment->valuesBase + ruleEnvironment->localsListAddr->nlocals;
            transformer_applyingRuleName = ruleEnvironment->name;

            if (options_option[verbose_p]) {
                fprintf (stderr, "    applying rule/function '%s'\n", *ident_idents[transformer_applyingRuleName]);
            }

            // attempt to recover
            if (transformer_callDepth != transformer_currentGCdepth) {
                if (options_option[verbose_p]) {
                    fprintf (stderr, "  (invoking garbage recovery)\n");
                }

                const int prevGCdepth = transformer_currentGCdepth;
                transformer_currentGCdepth = transformer_callDepth;
                transformer_nGarbageRecoveries += 1;

                if (options_option[verbose_p]) {
                    fprintf (stderr, "--- Recovering garbage ...\n");
                }

                garbageRecovery_recoverGarbage ();

                // now try the rule again
                if (options_option[verbose_p]) {
                    fprintf (stderr, "--- Retrying replacement in '%s'\n", *ident_idents[transformer_applyingRuleName]);
                }

                transformer_makeReplacement (replacementTP, subTreeTP, ruleEnvironment);

                if (options_option[verbose_p]) {
                    fprintf (stderr, "--- Completed retry of replacement in '%s'\n", 
                        *ident_idents[transformer_applyingRuleName]);
                }

                transformer_currentGCdepth = prevGCdepth;
                return;

            } else {
                error ("", "Repeated space failure in same replacement (a larger size is required for this transform)", FATAL, 507);
            }
        }

        throw (exception);
    }

}

static bool transformer_testCondition (const treePT replacementTP, struct transformer_ruleEnvironmentT *ruleEnvironment, const bool wantAll)
{
    assert (tree_trees[replacementTP].kind == treeKind_expression); 

    // the count field tells us the local symbol table index
    const int localIndex = tree_trees[replacementTP].count;
    treePT expressionTP = transformer_valueTP[ruleEnvironment->valuesBase + localIndex];

    const kidPT ruleCallsKP = tree_trees[replacementTP].kidsKP;

    assert (ruleCallsKP != nilKid); 

    bool someSuccess = false;
    bool allSuccess = false;

    transformer_applyRules (ruleCallsKP, ruleEnvironment, &expressionTP, &someSuccess, &allSuccess);

    if (wantAll) {
        return (allSuccess);
    } else {
        return (someSuccess);
    }
}

static void transformer_processParts (const tokenT ruleName, 
    const struct rulePartsT *prePostParts, struct transformer_ruleEnvironmentT *ruleEnvironment, bool *success)
{
    *success = true;

    for (int i = 1; i <= prePostParts->nparts; i++) {
        const struct rulePartT *part = &(rule_ruleParts[prePostParts->partsBase + i]);

        switch (part->kind) {

            case rulePart_construct:
                {
                    #ifdef DEBUGGER 
                    if (debugger_isbreakpoint (ruleName)) {
                        debugger_breakpoint (debug_constructEntry, ruleName, part->nameRef, nilTree, ruleEnvironment, false);
                    }
                    #endif

                    treePT resultTree = nilTree;
                    transformer_makeReplacement (part->replacementTP, &resultTree, ruleEnvironment);

                    transformer_valueTP[ruleEnvironment->valuesBase + part->nameRef] = resultTree;

                    #ifdef DEBUGGER 
                    if (debugger_isbreakpoint (ruleName)) {
                        debugger_breakpoint (debug_constructExit, ruleName, part->nameRef, resultTree, ruleEnvironment, false);
                    }
                    #endif
                }
                break;

            case rulePart_deconstruct:
                {
                    const treePT decValueTP = transformer_valueTP[ruleEnvironment->valuesBase + part->nameRef];

                    if (part->starred) {
                        if (part->skipName == NOT_FOUND) {
                            *success = transformer_searchTreeForDeconstructPattern (part->patternTP, decValueTP, ruleEnvironment);
                        } else {
                            if (part->skipRepeat) {
                                *success = transformer_searchTreeForDeconstructPatternSkippingRepeat (part->patternTP, decValueTP, 
                                    ruleEnvironment);
                            } else {
                                *success = transformer_searchTreeForDeconstructPatternSkipping (part->patternTP, decValueTP, 
                                    ruleEnvironment, part->skipName, part->skipName2, part->skipName3);
                            }
                        }
                    } else {
                        *success = transformer_matchTreeToPattern (part->patternTP, decValueTP, ruleEnvironment);
                    }

                    if (part->negated) {
                        *success = !(*success);
                    }

                    #ifdef DEBUGGER 
                    if (debugger_isbreakpoint (ruleName)) {
                        debugger_breakpoint (debug_deconstructExit, ruleName, part->nameRef, nilTree, ruleEnvironment, *success);
                    }
                    #endif
                }
                break;

            case rulePart_cond:
                {
                    *success = transformer_testCondition (part->replacementTP, ruleEnvironment, part->anded);

                    if (part->negated) {
                        *success = !(*success);
                    }

                    #ifdef DEBUGGER 
                    if (debugger_isbreakpoint (ruleName)) {
                        debugger_breakpoint (debug_conditionExit, ruleName, part->nameRef, nilTree, ruleEnvironment, *success);
                    }
                    #endif
                }
                break;

            case rulePart_assert:
                {
                    *success = transformer_testCondition (part->replacementTP, ruleEnvironment, part->anded);

                    if (part->negated) {
                        *success = !(*success);
                    }

                    #ifdef DEBUGGER 
                    if (debugger_isbreakpoint (ruleName)) {
                        debugger_breakpoint (debug_conditionExit, ruleName, part->nameRef, nilTree, ruleEnvironment, *success);
                    }
                    #endif

                    if (!(*success)) {
                        transformer_assert_error (ruleName, part->name);
                    }
                }
                break;

            case rulePart_import:
                {
                    struct transformer_ruleEnvironmentT *globalEnvironment = &(transformer_callEnvironment[0]);

                    const treePT impValueTP = transformer_valueTP[globalEnvironment->valuesBase + part->globalRef];
                    transformer_valueTP[ruleEnvironment->valuesBase + part->nameRef] = impValueTP;

                    if (impValueTP == nilTree) {
                        transformer_global_error (ruleName, part->name);
                    }

                    if (part->patternTP != nilTree) {
                        *success = transformer_matchTreeToPattern (part->patternTP, impValueTP, ruleEnvironment);
                    } else {
                        *success = true;
                    }

                    #ifdef DEBUGGER 
                    if (debugger_isbreakpoint (ruleName)) {
                        debugger_breakpoint (debug_importExit, ruleName, part->nameRef, 
                            transformer_valueTP[ruleEnvironment->valuesBase + part->nameRef], ruleEnvironment, *success);
                    }
                    #endif
                }
                break;

            case rulePart_export:
                {
                    #ifdef DEBUGGER 
                    if (debugger_isbreakpoint (ruleName)) {
                        debugger_breakpoint (debug_exportEntry, ruleName, part->nameRef, nilTree, ruleEnvironment, false);
                    }
                    #endif

                    struct transformer_ruleEnvironmentT *globalEnvironment = &(transformer_callEnvironment[0]);

                    if (part->replacementTP != nilTree) {
                        treePT resultTree = nilTree;
                        transformer_makeReplacement (part->replacementTP, &resultTree, ruleEnvironment);
                        transformer_valueTP[ruleEnvironment->valuesBase + part->nameRef] = resultTree;
                    }

                    // we always share the value of a global with its corresponding local
                    // (note this means we must be careful to copy every reference to the corresponding local!)
                    transformer_valueTP[globalEnvironment->valuesBase + part->globalRef] = 
                        transformer_valueTP[ruleEnvironment->valuesBase + part->nameRef];

                    ruleEnvironment->hasExported = true;

                    #ifdef DEBUGGER 
                        if (debugger_isbreakpoint (ruleName)) {
                            debugger_breakpoint (debug_exportExit, ruleName, part->nameRef, 
                                transformer_valueTP[ruleEnvironment->valuesBase + part->nameRef], ruleEnvironment, true);
                        }
                    #endif
                }
                break;

            default :
                {
                    error ("", "Fatal TXL error in processParts", INTERNAL_FATAL, 508);
                }
                break;
        }

        if (!(*success)) break;
    }
}

static bool transformer_searchTreeForPattern (const struct ruleT *rule, const treePT argTreeTP, kidPT *parentKP, 
    struct transformer_ruleEnvironmentT *ruleEnvironment)
{
    // Rationale for the order of the following logic is the typical frequency
    // profile of the cases in production use at Legasys.  Here is a sample:
    
    // kind of treeTP, per cycle :
    // empty             4789226        28.0%
    // repeat            3320065        19.4%
    // literal           2687817        15.7%
    // choose            2421533        14.2%
    // id                2021533        11.8%
    // order             1581074         9.2%
    // stringlit          250804         1.5%
    // charlit             15556         0.1%
    // number              15135         0.1%

    treePT treeTP = argTreeTP;
    treePT patternTP = rule->patternTP;
    int searchTop = transformer_searchTop;
    int searchBase = transformer_searchTop;

    if (tree_trees[patternTP].kind == treeKind_subsequentUse) {
        // use concrete pattern
        patternTP = transformer_valueTP[ruleEnvironment->valuesBase + tree_trees[patternTP].count];
    }

    while (true) {
        assert ((tree_trees[patternTP].kidsKP >= 0) && (tree_trees[patternTP].kidsKP <= maxKids));
        assert ((tree_trees[treeTP].kidsKP >= 0) && (tree_trees[treeTP].kidsKP <= maxKids));

        #ifdef PROFILER
            transformer_searchcycles += 1;
        #endif

        if (((tree_trees[treeTP].kind == tree_trees[patternTP].kind) || (tree_trees[patternTP].kind == treeKind_firstTime)) 
                && transformer_matchTreeToPattern (patternTP, treeTP, ruleEnvironment)) {

            #ifdef DEBUGGER 
            if (debugger_isbreakpoint (rule->name)) {
                debugger_breakpoint (debug_matchEntry, rule->name, 0, treeTP, ruleEnvironment, false);
            }
            #endif

            if (rule->postPattern.nparts > 0) {

                const int oldTreeCount = tree_treeCount;
                const int oldKidCount = tree_kidCount;
                bool yes;
                transformer_searchTop = searchTop;

                transformer_processParts (rule->name, &(rule->postPattern), ruleEnvironment, &yes);

                if (yes) {
                    transformer_searchTop = searchBase;
                    return (true);
                } else {
                    if ((tree_allocationStrategy == simple) && (!(ruleEnvironment->hasExported))) {
                        // recover any space we may have used in the post pattern
                        tree_setTreeCount (oldTreeCount);
                        tree_setKidCount (oldKidCount);
                    }
                }
            } else {
                transformer_searchTop = searchBase;
                return (true);
            }

            #ifdef DEBUGGER 
                const int nprelocals = ruleEnvironment->localsListAddr->nprelocals;
                const int nlocals = ruleEnvironment->localsListAddr->nlocals;
                for (int l = nprelocals + 1; l <= nlocals; l++) {
                    transformer_valueTP[ruleEnvironment->valuesBase + l] = nilTree;
                }
            #endif
        }

        if (tree_trees[treeTP].kind >= firstLeafKind) {
            // A terminal -
            // Pop any completed sequences ...
            while (true) {
                if (searchTop == searchBase) {
                    transformer_searchTop = searchBase;
                    return (false);
                }
                if (transformer_searchStack[searchTop].kidsKP < transformer_searchStack[searchTop].endKP) 
                    break;
                searchTop -= 1;
            }
            // ... and move on to the next subtree in the sequence
            assert (((searchTop > searchBase) 
                && (transformer_searchStack[searchTop].kidsKP < transformer_searchStack[searchTop].endKP)));
            transformer_searchStack[searchTop].kidsKP += 1;
            *parentKP = transformer_searchStack[searchTop].kidsKP;
            treeTP = tree_kids[*parentKP];

        } else if (tree_trees[treeTP].kind == treeKind_choose) {
            // One child - just go down to it (no need to come back)
            *parentKP = tree_trees[treeTP].kidsKP;
            treeTP = tree_kids[*parentKP];

        } else {
            // Push a new sequence of subtrees to check
            assert ((tree_trees[treeTP].kind == treeKind_order) || (tree_trees[treeTP].kind == treeKind_repeat) 
                || (tree_trees[treeTP].kind == treeKind_list));

            if (searchTop >= transformer_maxSearchDepth) {
                transformer_searchdepth_error (transformer_applyingRuleName);
            }

            searchTop += 1;
            transformer_searchStack[searchTop].kidsKP = tree_trees[treeTP].kidsKP;
            transformer_searchStack[searchTop].endKP = transformer_searchStack[searchTop].kidsKP + tree_trees[treeTP].count - 1;
            *parentKP = tree_trees[treeTP].kidsKP;
            treeTP = tree_kids[*parentKP];
        }
    }
}

static bool transformer_searchTreeForPatternSkipping (const struct ruleT *rule, const treePT argTreeTP, kidPT *parentKP, 
    struct transformer_ruleEnvironmentT *ruleEnvironment, const tokenT skipName, const tokenT skipName2, const tokenT skipName3)
{
    treePT treeTP = argTreeTP;
    treePT patternTP = rule->patternTP;
    int searchTop = transformer_searchTop;
    int searchBase = transformer_searchTop;

    if (tree_trees[patternTP].kind == treeKind_subsequentUse) {
        // use concrete pattern
        patternTP = transformer_valueTP[ruleEnvironment->valuesBase + tree_trees[patternTP].count];
    }

    while (true) {
        assert ((tree_trees[patternTP].kidsKP >= 0) && (tree_trees[patternTP].kidsKP <= maxKids));
        assert ((tree_trees[treeTP].kidsKP >= 0) && (tree_trees[treeTP].kidsKP <= maxKids));

        #ifdef PROFILER
            transformer_searchcycles += 1;
        #endif

        if (((tree_trees[treeTP].kind == tree_trees[patternTP].kind) || (tree_trees[patternTP].kind == treeKind_firstTime)) 
                && transformer_matchTreeToPattern (patternTP, treeTP, ruleEnvironment)) {

            #ifdef DEBUGGER 
            if (debugger_isbreakpoint (rule->name)) {
                debugger_breakpoint (debug_matchEntry, rule->name, 0, treeTP, ruleEnvironment, false);
            }
            #endif

            if (rule->postPattern.nparts > 0) {

                const int oldTreeCount = tree_treeCount;
                const int oldKidCount = tree_kidCount;
                bool yes;
                transformer_searchTop = searchTop;

                transformer_processParts (rule->name, &(rule->postPattern), ruleEnvironment, &yes);

                if (yes) {
                    transformer_searchTop = searchBase;
                    return (true);
                } else {
                    if ((tree_allocationStrategy == simple) && (!(ruleEnvironment->hasExported))) {
                        // recover any space we may have used in the post pattern
                        tree_setTreeCount (oldTreeCount);
                        tree_setKidCount (oldKidCount);
                    }
                }
            } else {
                transformer_searchTop = searchBase;
                return (true);
            }

            #ifdef DEBUGGER 
                const int nprelocals = ruleEnvironment->localsListAddr->nprelocals;
                const int nlocals = ruleEnvironment->localsListAddr->nlocals;
                for (int l = nprelocals + 1; l <= nlocals; l++) {
                    transformer_valueTP[ruleEnvironment->valuesBase + l] = nilTree;
                }
            #endif
        }

        if ((tree_trees[treeTP].kind >= firstLeafKind) || (tree_trees[treeTP].name == skipName) ||
                (tree_trees[treeTP].name == skipName2) || (tree_trees[treeTP].name == skipName3)) {
            // A terminal -
            // Pop any completed sequences ...
            while (true) {
                if (searchTop == searchBase) {
                    transformer_searchTop = searchBase;
                    return (false);
                }
                if (transformer_searchStack[searchTop].kidsKP < transformer_searchStack[searchTop].endKP) 
                    break;
                searchTop -= 1;
            }
            // ... and move on to the next subtree in the sequence
            assert (((searchTop > searchBase) 
                && (transformer_searchStack[searchTop].kidsKP < transformer_searchStack[searchTop].endKP)));
            transformer_searchStack[searchTop].kidsKP += 1;
            *parentKP = transformer_searchStack[searchTop].kidsKP;
            treeTP = tree_kids[*parentKP];

        } else if (tree_trees[treeTP].kind == treeKind_choose) {
            // One child - just go down to it (no need to come back)
            *parentKP = tree_trees[treeTP].kidsKP;
            treeTP = tree_kids[*parentKP];

        } else {
            // Push a new sequence of subtrees to check
            assert ((tree_trees[treeTP].kind == treeKind_order) || (tree_trees[treeTP].kind == treeKind_repeat) 
                || (tree_trees[treeTP].kind == treeKind_list));

            if (searchTop >= transformer_maxSearchDepth) {
                transformer_searchdepth_error (transformer_applyingRuleName);
            }

            searchTop += 1;
            transformer_searchStack[searchTop].kidsKP = tree_trees[treeTP].kidsKP;
            transformer_searchStack[searchTop].endKP = transformer_searchStack[searchTop].kidsKP + tree_trees[treeTP].count - 1;
            *parentKP = tree_trees[treeTP].kidsKP;
            treeTP = tree_kids[*parentKP];
        }
    }
}

static bool transformer_searchTreeForPatternSkippingRepeat (const struct ruleT *rule, const treePT argTreeTP, kidPT *parentKP, 
    struct transformer_ruleEnvironmentT *ruleEnvironment)
{
    treePT treeTP = argTreeTP;
    treePT patternTP = rule->patternTP;

    if (tree_trees[patternTP].kind == treeKind_subsequentUse) {
        // use concrete pattern
        patternTP = transformer_valueTP[ruleEnvironment->valuesBase + tree_trees[patternTP].count];
    }

    // walk the repeat looking for the matching element
    while (true) {
        if (tree_trees[tree_kids[tree_trees[treeTP].kidsKP]].kind == treeKind_empty) break;

        #ifdef PROFILER
            transformer_searchcycles += 1;
        #endif

        *parentKP = tree_trees[treeTP].kidsKP;
        const treePT elementTP = tree_kids[*parentKP];

        if (((tree_trees[elementTP].kind == tree_trees[patternTP].kind) || (tree_trees[patternTP].kind == treeKind_firstTime)) 
                && transformer_matchTreeToPattern (patternTP, elementTP, ruleEnvironment)) {
            #ifdef DEBUGGER 
            if (debugger_isbreakpoint (rule->name)) {
                debugger_breakpoint (debug_matchEntry, rule->name, 0, treeTP, ruleEnvironment, false);
            }
            #endif

            if (rule->postPattern.nparts > 0) {
                const int oldTreeCount = tree_treeCount;
                const int oldKidCount = tree_kidCount;
                bool yes;

                transformer_processParts (rule->name, &(rule->postPattern), ruleEnvironment, &yes);

                if (yes) {
                    return (true);
                } else {
                    if ((tree_allocationStrategy == simple) && (!(ruleEnvironment->hasExported))) {
                        // recover any space we may have used in the post pattern
                        tree_setTreeCount (oldTreeCount);
                        tree_setKidCount (oldKidCount);
                    }
                }

            } else {
                return (true);
            }

            #ifdef DEBUGGER 
                const int nprelocals = ruleEnvironment->localsListAddr->nprelocals;
                const int nlocals = ruleEnvironment->localsListAddr->nlocals;
                for (int l = nprelocals + 1; l <= nlocals; l++) {
                    transformer_valueTP[ruleEnvironment->valuesBase + l] = nilTree;
                }
            #endif
        }

        treeTP = tree_kids[(tree_trees[treeTP].kidsKP) + 1];
    }

    return (false);
}

static void transformer_applyRuleWhileMatch (const struct ruleT *rule, struct transformer_ruleEnvironmentT *ruleEnvironment, 
    const treePT originalTP, treePT *resultTP, bool *matchedAtLeastOnce)
{
    *resultTP = originalTP;

    const int oldTreeCount = tree_treeCount;
    const int oldKidCount = tree_kidCount;

    bool matched;
    *matchedAtLeastOnce = false;

    if (rule->prePattern.nparts > 0) {
        transformer_processParts (rule->name, &(rule->prePattern), ruleEnvironment, &matched);

        if (!matched) {
            if ((tree_allocationStrategy == simple) && (!(ruleEnvironment->hasExported))) {
                // recover any space we may have used in the post pattern
                tree_setTreeCount (oldTreeCount);
                tree_setKidCount (oldKidCount);
            }
            return;
        }
    }

    bool firstTime = true;
    matched = false;

    while (true) {
        kidPT parentKP = nilKid;

        if (rule->skipName == NOT_FOUND) {
            matched = transformer_searchTreeForPattern (rule, *resultTP, &parentKP, ruleEnvironment);
        } else if (rule->skipRepeat) {
            matched = transformer_searchTreeForPatternSkippingRepeat (rule, *resultTP, &parentKP, ruleEnvironment);
        } else {
            matched = transformer_searchTreeForPatternSkipping (rule, *resultTP, &parentKP, ruleEnvironment, 
                rule->skipName, rule->skipName2, rule->skipName3);
        }

        if (!matched) {
            if (firstTime) {
                if ((tree_allocationStrategy == simple) && (!(ruleEnvironment->hasExported))) {
                    tree_setTreeCount (oldTreeCount);
                    tree_setKidCount (oldKidCount);
                }
            }
            return;
        }

        *matchedAtLeastOnce = true;

        if (rule->replacementTP == nilTree) {
            // a match rule that succeeded
            assert (matched);
            if ((tree_allocationStrategy == simple) && (!(ruleEnvironment->hasExported))) {
                // recover any space we may have used in the post pattern
                tree_setTreeCount (oldTreeCount);
                tree_setKidCount (oldKidCount);
            }
            return;
        }

        if (parentKP == nilKid) {
            transformer_makeReplacement (rule->replacementTP, resultTP, ruleEnvironment);
            // this will become the new scope when we are done -
            // so make sure that the garbage collector knows about it
            ruleEnvironment->newscopeTP = *resultTP;
        } else {
            treePT replacedKidTP = tree_kids[parentKP];
            transformer_makeReplacement (rule->replacementTP, &replacedKidTP, ruleEnvironment);
            tree_setKidTree (parentKP, replacedKidTP);
        }

        #ifdef DEBUGGER 
            if (debugger_isbreakpoint (rule->name)) {
                treePT replacementResultTP = *resultTP;
                if (parentKP != nilKid) {
                    replacementResultTP = tree_kids[parentKP];
                }
                debugger_breakpoint (debug_matchExit, rule->name, 0, replacementResultTP, ruleEnvironment, true);
            }
        #endif

        firstTime = false;
    }
}

static void transformer_applyRuleOnceOnly (const struct ruleT *rule, struct transformer_ruleEnvironmentT *ruleEnvironment, 
    const treePT originalTP, treePT *resultTP, bool *matched)
{
    *resultTP = originalTP;

    const int oldTreeCount = tree_treeCount;
    const int oldKidCount = tree_kidCount;


    if (rule->prePattern.nparts > 0) {
        transformer_processParts (rule->name, &(rule->prePattern), ruleEnvironment, matched);

        if (!(*matched)) {
            if ((tree_allocationStrategy == simple) && (!(ruleEnvironment->hasExported))) {
                // recover any space we may have used in the post pattern
                tree_setTreeCount (oldTreeCount);
                tree_setKidCount (oldKidCount);
            }
            return;
        }
    }

    kidPT parentKP = nilKid;

    if (!(rule->starred)) {
        *matched = transformer_matchTreeToPattern (rule->patternTP, *resultTP, ruleEnvironment);

        if (!(*matched)) {
            if ((tree_allocationStrategy == simple) && (!(ruleEnvironment->hasExported))) {
                // recover any space we may have used in the post pattern
                tree_setTreeCount (oldTreeCount);
                tree_setKidCount (oldKidCount);
            }
            return;
        }

        #ifdef DEBUGGER 
        if (debugger_isbreakpoint (rule->name)) {
            debugger_breakpoint (debug_matchEntry, rule->name, 0, *resultTP, ruleEnvironment, false);
        }
        #endif

        if (rule->postPattern.nparts > 0) {
            transformer_processParts (rule->name, &(rule->postPattern), ruleEnvironment, matched);
        }

    } else if (rule->skipName == NOT_FOUND) {
        *matched = transformer_searchTreeForPattern (rule, *resultTP, &parentKP, ruleEnvironment);
    } else if (rule->skipRepeat) {
        *matched = transformer_searchTreeForPatternSkippingRepeat (rule, *resultTP, &parentKP, ruleEnvironment);
    } else {
        *matched = transformer_searchTreeForPatternSkipping (rule, *resultTP, &parentKP, ruleEnvironment, 
            rule->skipName, rule->skipName2, rule->skipName3);
    }

    if (!(*matched)) {
        if ((tree_allocationStrategy == simple) && (!(ruleEnvironment->hasExported))) {
            // recover any space we may have used in the post pattern
            tree_setTreeCount (oldTreeCount);
            tree_setKidCount (oldKidCount);
        }
        return;
    }

    if (rule->replacementTP == nilTree) {
        // a match function that succeeded
        if ((tree_allocationStrategy == simple) && (!(ruleEnvironment->hasExported))) {
            // recover any space we may have used in the post pattern
            tree_setTreeCount (oldTreeCount);
            tree_setKidCount (oldKidCount);
        }
        return;
    }

    if (parentKP == nilKid) {
        transformer_makeReplacement (rule->replacementTP, resultTP, ruleEnvironment);
        // this will become the new scope when we are done -
        // so make sure that the garbage collector knows about it
        ruleEnvironment->newscopeTP = *resultTP;
    } else {
        treePT resultKidTP = tree_kids[parentKP];
        transformer_makeReplacement (rule->replacementTP, &resultKidTP, ruleEnvironment);
        tree_setKidTree (parentKP, resultKidTP);
    }

    #ifdef DEBUGGER 
        if (debugger_isbreakpoint (rule->name)) {
            debugger_breakpoint (debug_matchExit, rule->name, 0, *resultTP, ruleEnvironment, true);
        }
    #endif
}

static void transformer_termination_error (const tokenT ruleName)
{
    string context;
    stringprintf (context, "rule/function '%s'", *ident_idents[ruleName]);
    error (context, "One pass rule failed to terminate (probable cause: part of replacement matches pattern)", FATAL, 509);
}

static void transformer_applyRuleOnePass (const struct ruleT *rule, struct transformer_ruleEnvironmentT *ruleEnvironment, 
    const treePT originalTP, treePT *resultTP, bool *matchedAtLeastOnce)
{
    *resultTP = originalTP;

    bool matched;
    *matchedAtLeastOnce = false;

    if (rule->prePattern.nparts > 0) {
        const int oldTreeCount = tree_treeCount;
        const int oldKidCount = tree_kidCount;

        transformer_processParts (rule->name, &(rule->prePattern), ruleEnvironment, &matched);

        if (!matched) {
            if ((tree_allocationStrategy == simple) && (!(ruleEnvironment->hasExported))) {
                // recover any space we may have used in the post pattern
                tree_setTreeCount (oldTreeCount);
                tree_setKidCount (oldKidCount);
            }
            return;
        }
    }

    // Rationale for the order of the following logic is the typical frequency
    // profile of the cases in production use at Legasys.  Here is a sample:
    
    // kind of treeTP, per cycle :
    // empty             2473860        29.4%
    // choose            1522578        18.1%
    // repeat            1512659        18.0%
    // order             1017587        12.1%
    // literal           1014848        12.1%
    // id                 762896         9.1%
    // stringlit           74698         0.9%
    // number              15054         0.2%
    // charlit             12667         0.2%

    treePT treeTP = *resultTP;
    treePT patternTP = rule->patternTP;
    int searchTop = transformer_searchTop;
    int searchBase = transformer_searchTop;
    kidPT parentKP = nilKid;

    if (tree_trees[patternTP].kind == treeKind_subsequentUse) {
        // use the concrete pattern
        patternTP = transformer_valueTP[ruleEnvironment->valuesBase + tree_trees[patternTP].count];
    }

    while (true) {
        assert ((tree_trees[patternTP].kidsKP >= 0) && (tree_trees[patternTP].kidsKP <= maxKids));
        assert ((tree_trees[treeTP].kidsKP >= 0) && (tree_trees[treeTP].kidsKP <= maxKids));

        #ifdef PROFILER
            transformer_searchcycles += 1;
        #endif

        matched = ((tree_trees[treeTP].kind == tree_trees[patternTP].kind) || (tree_trees[patternTP].kind == treeKind_firstTime)) 
            && transformer_matchTreeToPattern (patternTP, treeTP, ruleEnvironment);

        if (matched) {
            #ifdef DEBUGGER 
                if (debugger_isbreakpoint (rule->name)) {
                    debugger_breakpoint (debug_matchEntry, rule->name, 0, treeTP, ruleEnvironment, false);
                }
            #endif

            if (rule->postPattern.nparts > 0) {
                const int oldTreeCount = tree_treeCount;
                const int oldKidCount = tree_kidCount;

                transformer_searchTop = searchTop;
                transformer_processParts (rule->name, &(rule->postPattern), ruleEnvironment, &matched);

                if (!matched) {
                    #ifdef DEBUGGER 
                        const int nprelocals = ruleEnvironment->localsListAddr->nprelocals;
                        const int nlocals = ruleEnvironment->localsListAddr->nlocals;
                        for (int l = nprelocals + 1; l <= nlocals; l++) {
                            transformer_valueTP[ruleEnvironment->valuesBase + l] = nilTree;
                        }
                    #endif

                    if ((tree_allocationStrategy == simple) && (!(ruleEnvironment->hasExported))) {
                        // recover any space we may have used in the post pattern
                        tree_setTreeCount (oldTreeCount);
                        tree_setKidCount (oldKidCount);
                    }
                }
            }

            if (matched) {
                *matchedAtLeastOnce = true;
                transformer_searchTop = searchTop;

                // this might be a visitor-only match $ rule, so there may not be a replacement
                if (rule->replacementTP != nilTree) {

                    if (parentKP == nilKid) {
                        transformer_makeReplacement (rule->replacementTP, resultTP, ruleEnvironment);
                        treeTP = *resultTP;
                        // this will become the new scope when we are done -
                        // so make sure that the garbage collector knows about it
                        ruleEnvironment->newscopeTP = *resultTP;
                    } else {
                        treePT resultKidTP = tree_kids[parentKP];
                        transformer_makeReplacement (rule->replacementTP, &resultKidTP, ruleEnvironment);
                        tree_setKidTree (parentKP, resultKidTP);
                        treeTP = resultKidTP;
                    }
                }

                #ifdef DEBUGGER 
                    if (debugger_isbreakpoint (rule->name)) {
                        debugger_breakpoint (debug_matchExit, rule->name, 0, treeTP, ruleEnvironment, true);
                    }
                #endif
            }
        }

        if ((tree_trees[treeTP].kind >= firstLeafKind) || (tree_trees[treeTP].name == rule->skipName) ||
                (tree_trees[treeTP].name == rule->skipName2) || (tree_trees[treeTP].name == rule->skipName3)) {
            // A terminal -
            // Pop any completed sequences ...
            while (true) {
                if (searchTop == searchBase) {
                    transformer_searchTop = searchBase;
                    return;
                }
                if (transformer_searchStack[searchTop].kidsKP < transformer_searchStack[searchTop].endKP) 
                    break;
                searchTop -= 1;
            }
            // ... and move on to the next subtree in the sequence
            assert ((searchTop > searchBase) && (transformer_searchStack[searchTop].kidsKP < transformer_searchStack[searchTop].endKP));

            transformer_searchStack[searchTop].kidsKP += 1;
            parentKP = transformer_searchStack[searchTop].kidsKP;
            treeTP = tree_kids[parentKP];

        } else if (tree_trees[treeTP].kind == treeKind_choose) {
            // One child - just go down to it (no need to come back)
            parentKP = tree_trees[treeTP].kidsKP;
            treeTP = tree_kids[parentKP];

        } else {
            // Push a new sequence of subtrees to check
            assert ((tree_trees[treeTP].kind == treeKind_order) || (tree_trees[treeTP].kind == treeKind_repeat) 
                || (tree_trees[treeTP].kind == treeKind_list));

            if (searchTop >= transformer_maxSearchDepth) {
                // this is impossible, so the replacement must match the pattern!
                transformer_termination_error (transformer_applyingRuleName);
            }

            searchTop += 1;
            transformer_searchStack[searchTop].kidsKP = tree_trees[treeTP].kidsKP;
            transformer_searchStack[searchTop].endKP = transformer_searchStack[searchTop].kidsKP + tree_trees[treeTP].count - 1;
            parentKP = tree_trees[treeTP].kidsKP;
            treeTP = tree_kids[parentKP];
        }
    }
}

// Predefined functions
#include "predefs.h"

static void transformer_applyRule (const int ruleIndex, struct transformer_ruleEnvironmentT *ruleEnvironment, 
    const treePT originalTP, treePT *resultTP, bool *matched)
{
    // Stack use limitation - to avoid crashes
    checkstack ();

    const struct ruleT *rule = &(rule_rules[ruleIndex]);

    transformer_callingRuleName = transformer_applyingRuleName;
    transformer_applyingRuleName = rule->name;

    assert (ruleEnvironment->depth == transformer_callDepth);  

    #ifdef DEBUGGER 
        const struct ruleLocalsT *ruleLocals = ruleEnvironment->localsListAddr;
        for (int l = ruleLocals->nformals + 1; l <= ruleLocals->nlocals; l++) {
            transformer_valueTP[ruleEnvironment->valuesBase + l] = nilTree;
        }

        if (debugger_isbreakpoint (rule->name)) {
            debugger_breakpoint (debug_ruleEntry, rule->name, 0, originalTP, ruleEnvironment, false);
        }
    #endif

    const int oldTreeCount = tree_treeCount;
    const int oldKidCount = tree_kidCount;

    ruleEnvironment->hasExported = false;

    #ifdef PROFILER 
        struct transformer_ruleStatisticsT *ruleStats = &(transformer_ruleStatistics[ruleIndex]);
        struct transformer_ruleStatisticsT oldStats;
        oldStats.searchcycles = ruleStats->searchcycles;
        oldStats.matchcycles = ruleStats->matchcycles;
        oldStats.trees = ruleStats->trees;
        oldStats.kids = ruleStats->kids;
        struct transformer_ruleStatisticsT startStats;
        startStats.searchcycles = transformer_searchcycles;
        startStats.matchcycles = transformer_matchcycles;
        startStats.trees = tree_treeCount;
        startStats.kids = tree_kidCount;
#endif

    if (options_option[rule_print_p]) {
        string callIndent;
        substring (callIndent, BLANKS, 1, transformer_callDepth-1);
        fprintf (stderr, "%sEntering rule %s\n", callIndent, *ident_idents[rule->name]);
    }

    switch (rule->kind) {
        case ruleKind_rule:
            {
                transformer_applyRuleWhileMatch (rule, ruleEnvironment, originalTP, resultTP, matched);
            }
            break;
        case ruleKind_function:
            {
                transformer_applyRuleOnceOnly (rule, ruleEnvironment, originalTP, resultTP, matched);
            }
            break;
        case ruleKind_onepass:
            {
                transformer_applyRuleOnePass (rule, ruleEnvironment, originalTP, resultTP, matched);
            }
            break;
        case ruleKind_predefined:
            {
                predefs_applyPredefinedFunction (ruleIndex, ruleEnvironment, originalTP, resultTP, matched);
            }
            break;
    }

    #ifdef PROFILER 
        ruleStats->calls += 1;
        if (*matched) {
            ruleStats->matches += 1;
        }
        ruleStats->searchcycles = oldStats.searchcycles + (transformer_searchcycles - startStats.searchcycles);
        ruleStats->matchcycles = oldStats.matchcycles + (transformer_matchcycles - startStats.matchcycles);
        ruleStats->trees = oldStats.trees + (tree_treeCount - startStats.trees);
        ruleStats->kids = oldStats.kids + (tree_kidCount - startStats.kids);
    #endif

    if (options_option[rule_print_p]) {
        string callIndent;
        substring (callIndent, BLANKS, 1, transformer_callDepth-1);
        fprintf (stderr, "%sExiting rule %s", callIndent, *ident_idents[rule->name]);
        if (*matched) {
            fprintf (stderr, " (succeeded) ");
        } else {
            fprintf (stderr, " (failed) ");
        }
        #ifndef DEBUGGER
        if (options_option[verbose_p]) {
        #endif
            fprintf (stderr, "- %d trees, %d kids", (tree_treeCount - oldTreeCount), (tree_kidCount - oldKidCount));
        #ifndef DEBUGGER
        }
        #endif
        fprintf (stderr, "\n");
    }

    #ifdef DEBUGGER 
        if (debugger_isbreakpoint (rule->name)) {
            debugger_breakpoint (debug_ruleExit, rule->name, 0, *resultTP, ruleEnvironment, *matched);
        }
    #endif

    assert (ruleEnvironment->depth == transformer_callDepth);
}

static void transformer_recursion_error (const tokenT ruleName)
{
    string context;
    stringprintf (context, "rule/function '%s'", *ident_idents[ruleName]);
    error (context, "Transform recursion limit exceeded (Probable cause: infinite recursion, small size or stack limit)", LIMIT_FATAL, 510);
}

static void transformer_interrupt_error (const tokenT ruleName)
{
    string context;
    stringprintf (context, "rule/function '%s'", *ident_idents[ruleName]);
    error (context, "Transform interrupted by user", FATAL, 511);
}

static void transformer_fatal_error (const tokenT ruleName)
{
    string context;
    stringprintf (context, "rule/function '%s'", *ident_idents[ruleName]);
    error (context, "Fatal TXL error (signal)", DEFERRED, 512);
}

static void transformer_garbage_warning (void) {
    string message;
    stringprintf (message, "%d garbage recoveries were required (a larger size is recommended for improved performance)", 
        transformer_nGarbageRecoveries);
    error ("", message, WARNING, 513);
}

static tokenT transformer_install_as_string (const string id)
{
    string idstring;
    stringprintf (idstring, "\"%s\"", id);
    return (ident_install (idstring, treeKind_stringlit));
}

void transformer_applyMainRule (const treePT originalInputParseTreeTP, treePT *transformedInputParseTreeTP)
{
    if (!(rule_rules[mainRule].defined)) {
        // Parsing only - TXL 10.7
        *transformedInputParseTreeTP = originalInputParseTreeTP;
        return;
    }

    try {

        // Remember treespace used by the compiled TXL program, so it's not disturbed by garbage collection
        transformer_lastCompileTree = tree_treeCount;
        transformer_lastCompileKid = tree_kidCount;

        #ifdef PROFILER 
            for (int r = 1; r <= rule_nRules; r++) {
                struct transformer_ruleStatisticsT *ruleStats = &(transformer_ruleStatistics[r]);
                ruleStats->calls = 0;
                ruleStats->matches = 0;
                ruleStats->searchcycles = 0;
                ruleStats->matchcycles = 0;
                ruleStats->trees = 0;
                ruleStats->kids = 0;
            }
            transformer_searchcycles = 0;
            transformer_matchcycles = 0;
        #endif

        // initialize the rule call stack
        struct transformer_ruleEnvironmentT *globalEnvironment = &(transformer_callEnvironment[0]);
        struct transformer_ruleEnvironmentT *mainEnvironment = &(transformer_callEnvironment[1]);

        transformer_callDepth = 1;

        // initialize the globals symbol table
        globalEnvironment->depth = 0;
        globalEnvironment->valuesBase = transformer_valueCount;
        transformer_valueCount += rule_rules[globalR].localVars.nlocals;

        globalEnvironment->name = rule_rules[globalR].name;
        globalEnvironment->localsListAddr = &(rule_rules[globalR].localVars);
        globalEnvironment->scopeTP = nilTree;
        globalEnvironment->resultTP = nilTree;
        globalEnvironment->newscopeTP = nilTree;

        const tokenT repeat_0_stringlit_T = ident_install ("repeat_0_stringlit", treeKind_id);
        const int repeat_0_stringlit_index = symbol_lookupSymbol (repeat_0_stringlit_T);
        assert (repeat_0_stringlit_index != NOT_FOUND);

        // its tokens are the program arguments as strings
        lastTokenIndex = 0;

        for (int pa = 1; pa <= options_nProgArgs; pa++) {
            lastTokenIndex += 1;
            inputTokens[lastTokenIndex].token = ident_install (options_progArgs[pa], treeKind_stringlit);
            inputTokens[lastTokenIndex].rawtoken = inputTokens[lastTokenIndex].token;
            inputTokens[lastTokenIndex].kind = treeKind_stringlit;
        }

        lastTokenIndex += 1;
        inputTokens[lastTokenIndex].token = empty_T;
        inputTokens[lastTokenIndex].rawtoken = empty_T;
        inputTokens[lastTokenIndex].kind = treeKind_empty;

        // parse them as a sequence of stringlits
        treePT progArgsTP = nilTree;
        parser_initializeParse ("command line arguments", false, false, false, (struct ruleLocalsT *) 0, (* (parser_parseVarOrExpProc *) 0));
        parser_parse (symbol_symbols[repeat_0_stringlit_index], &progArgsTP);

        // make sure that we got a parse
        assert (progArgsTP != nilTree);

        // initialize the new (version 10) predefined global variables

        // initialize the global variable TXLargs
        treePT TXLargsTP;
        tree_copyTree (progArgsTP, &TXLargsTP);
        transformer_valueTP[globalEnvironment->valuesBase + 1] = TXLargsTP;

        // initialize the global variable TXLprogram
        const tokenT TXLprogramT = transformer_install_as_string (options_txlSourceFileName);
        const treePT TXLprogramTP = tree_newTreeInit (treeKind_stringlit, TXLprogramT, TXLprogramT, 0, nilKid);
        transformer_valueTP[globalEnvironment->valuesBase + 2] = TXLprogramTP;

        // initialize the global variable TXLinput
        const tokenT TXLinputT = transformer_install_as_string (options_inputSourceFileName);
        const treePT TXLinputTP = tree_newTreeInit (treeKind_stringlit, TXLinputT, TXLinputT, 0, nilKid);
        transformer_valueTP[globalEnvironment->valuesBase + 3] = TXLinputTP;

        // initialize the global variable TXLexitcode
        const tokenT TXLexitcodeT = ident_install ("0", treeKind_number);
        const treePT TXLexitcodeTP = tree_newTreeInit (treeKind_number, TXLexitcodeT, TXLexitcodeT, 0, nilKid);
        transformer_valueTP[globalEnvironment->valuesBase + 4] = TXLexitcodeTP;

        // nil out the other global variables, if any
        for (int glob = 5; glob <= rule_rules[globalR].localVars.nlocals; glob++) {
            transformer_valueTP[globalEnvironment->valuesBase + glob] = nilTree;
        }

        mainEnvironment->depth = 1;

        // new value binding protocol
        mainEnvironment->valuesBase = transformer_valueCount;
        transformer_valueCount += rule_rules[mainRule].localVars.nlocals;

        // remember the name of the main rule (for debugging)
        mainEnvironment->name = rule_rules[mainRule].name;

        // attach the local symbol table for the main rule
        mainEnvironment->localsListAddr = &(rule_rules[mainRule].localVars);

        // remember the original scope tree
        mainEnvironment->scopeTP = originalInputParseTreeTP;

        // and the partially resolved replacement
        mainEnvironment->resultTP = nilTree;

        // and the partially resolved new scope
        mainEnvironment->newscopeTP = nilTree;

        // nil out the unbound main rule locals
        for (int loc = 1; loc <= rule_rules[mainRule].localVars.nlocals; loc++) {
            transformer_valueTP[mainEnvironment->valuesBase + loc] = nilTree;
        }

        // this is what running a TXL program means - apply the main rule!
        #ifdef DEBUGGER 
            // new protocol - default to on!
            debugger_breakpoint (debug_startup, rule_rules[mainRule].name, 0, originalInputParseTreeTP, mainEnvironment, false);
        #endif

        bool dontCareAboutSuccess;
        transformer_applyRule (mainRule, mainEnvironment, originalInputParseTreeTP, transformedInputParseTreeTP, 
            &dontCareAboutSuccess);

        int result = stringint (*ident_idents[tree_trees[transformer_valueTP[globalEnvironment->valuesBase + 4]].name]);
        exitcode = result;

        #ifdef DEBUGGER 
            debugger_breakpoint (debug_shutdown, rule_rules[mainRule].name, 0, *transformedInputParseTreeTP, mainEnvironment, false);
        #endif

        if ((options_option[verbose_p]) && ((transformer_copies + transformer_noncopies) > 0)) {
            fprintf (stderr, "Forced to copy %d local vars (%d%%)\n", transformer_copies, 
                ((transformer_copies * 100) / (transformer_copies + transformer_noncopies)));
        }

        if (transformer_nGarbageRecoveries > 4) {
            transformer_garbage_warning ();
        }

        #ifdef PROFILER
        int profout;
        tfopen (OPEN_CHAR_WRITE, "txl.rprofout", &profout);
        if (profout != 0) {
            fprintf (tffile (profout), "%s", "name calls matches searchcycles matchcycles trees kids");
            fprintf (tffile (profout), "\n");

            for (int r = 1; r <= rule_nRules; r++) {
                const struct transformer_ruleStatisticsT *ruleStats = &(transformer_ruleStatistics[r]);
                fprintf (tffile (profout), "%s %d %d %d %d %d %d\n", *ident_idents[rule_rules[r].name],
                    ruleStats->calls, ruleStats->matches, ruleStats->searchcycles, ruleStats->matchcycles,
                    ruleStats->trees, ruleStats->kids);
            }
            tfclose (profout);

        } else {
            error("", "Unable to create TXL profile file 'txl.rprofout'", FATAL, 514);
        }
        #endif

    } catch {

        if ((exception == OUTOFKIDS) || (exception == OUTOFTREES)) {
            throw (QUIT);
        } else if (exception == STACKLIMIT) {
            transformer_recursion_error (transformer_applyingRuleName);
        } else if (exception == INTERRUPT) {
            transformer_interrupt_error (transformer_applyingRuleName);
        } else if ((exception != QUIT) && (transformer_applyingRuleName != quit_T)) {
            transformer_fatal_error (transformer_applyingRuleName);
        }
        throw (exception);
    }
}

// Initialization
void transformer (void) {
    transformer_maxTotalValues = maxCallDepth * avgLocalVars;
    // 1-origin, [1 .. transformer_maxTotalValues]
    arrayalloc (transformer_maxTotalValues + 1, treePT, transformer_valueTP);
    transformer_valueTP[0] = UNUSED;
    transformer_valueCount = 0;

    arrayalloc ((maxCallDepth + 1), struct transformer_ruleEnvironmentT, transformer_callEnvironment);
    transformer_callEnvironment[0].name = UNUSED;
    transformer_callDepth = 0;

    transformer_maxSearchDepth = maxParseDepth * 4;
    arrayalloc (transformer_maxSearchDepth + 1, struct transformer_searchStackEntry, transformer_searchStack);
    transformer_searchStack[0].kidsKP = UNUSED;
    transformer_searchTop = 0;

    transformer_maxMatchDepth = maxParseDepth;
    arrayalloc (transformer_maxMatchDepth + 1, struct transformer_matchStackEntry, transformer_matchStack);
    transformer_matchStack[0].patternKidsKP = UNUSED;

#ifdef PROFILER
    arrayalloc (maxRules + 1, struct transformer_ruleStatisticsT, transformer_ruleStatistics);
    transformer_ruleStatistics[0].calls = UNUSED;
#endif

    transformer_applyingRuleName = empty_T;
    transformer_callingRuleName = empty_T;

    transformer_copies = 0;
    transformer_noncopies = 0;

    transformer_lastCompileTree = nilTree;
    transformer_lastCompileKid = nilKid;

    transformer_nGarbageRecoveries = 0;
    transformer_currentGCdepth = 0;

    predefs_initializePredefs ();

#ifdef DEBUGGER
    debugger_initializeDebugger ();
#endif
}
